Two point one sided rendezvous

In a rendezvous search two or more teams called seekers try to minimize the time needed to find each other. In this paper, we consider two seekers in the plane. This is a one sided problem since Seeker 1 begins at a predetermined point O  . Seeker 2 begins at one of a finite set of points _xi$x_i$ with probability _pi$p_i$. We first discuss the general situation and then consider the specific case when Seeker 2 can begin from one of two points.     

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

Objective Function Features Providing Barriers to Rapid Global Optimization

The purposes of this discussion paper are twofold. First, features of an objective function landscape which provide barriers to rapid finding of the global optimum are described. Second, stochastic algorithms are discussed and their performance examined, both theoretically and computationally, as the features change. The paper lays a foundation for the later findings paper.     

On finding mixed orthogonal arrays of strength 2 with many 2-level factors

We describe a method for finding mixed orthogonal arrays of strength 2 with a large number of 2-level factors. The method starts with an orthogonal array of strength 2, possibly tight, that contains mostly 2-level factors. By a computer search of this starting array, we attempt to find as large a number of 2-level factors as possible that can be used in a new orthogonal array of strength 2 containing one additional factor at more than two levels. The method produces new orthogonal arrays for some parameters, and matches the best-known arrays for others. It is especially useful for finding arrays with one or two factors at more than two levels.     

A Point Balance Algorithm for the Spherical Code Problem

The Spherical Code (SC) problem has many important applications in such fields as physics, molecular biology, signal transmission, chemistry, engineering and mathematics. This paper presents a bilevel optimization formulation of the SC problem. Based on this formulation, the concept of balanced spherical code is introduced and a new approach, the Point Balance Algorithm (PBA), is presented to search for a 1-balanced spherical code. Since an optimal solution of the SC problem (an extremal spherical code) must be a 1-balanced spherical code, PBA can be applied easily to search for an extremal spherical code. In addition, given a certain criterion, PBA can generate efficiently an approximate optimal spherical code on a sphere in the n-dimensional space ⁿ. Some implementation issues of PBA are discussed and putative global optimal solutions of the Fekete problem in 3, 4 and 5-dimensional space are also reported. Finally, an open question about the geometry of Fekete points on the unit sphere in the 3-dimensional space is posed.     

一种有机质谱谱图的库检索新算法

一种有机质谱谱图的库检索新算法律祥俊，林少凡，张金碚，张法义（南开大学中心实验室，天津，３０００７１）关键词检索，算法，质谱，数据库利用计算机匹配技术识别有机质谱谱图中的库检索方法仅需用低分辨质谱图即可识别未知化合物，似为最成功的方法［１～３］．质谱...     

基于CouchDB和Elastic Search的高性能化学结构搜索引擎与数据库的构建

计算机辅助的化学结构搜索在化学信息学中地位十分重要,本文设计了一套高性能的化学结构和化学数据搜索系统,称为DCAIKU.DCAIKU基于CouchDB无模式数据库和ElasticSearch基础架构构建,通过将结构相似性搜索变换为文字搜索实现了高性能和高灵活性的检索引擎：在满足化学信息存储的高灵活性条件下,仍然可以做到低延迟和高准确性,同时拥有良好的伸缩性,可以大规模并行化和集群化.     

Establishment of a search library about benzylisoquinoline alkaloids based on selective separation on the binaphthyl column and standard analysis on C18 column

A search library about benzylisoquinoline alkaloids was established based on preparation of alkaloid fractions from Rhizoma coptidis, Cortex phellodendri, and Rhizoma corydalis. In this work, two alkaloid fractions from each herbal medicine were first prepared based on selective separation on the “click” binaphthyl column. And then these alkaloid fractions were analyzed on C18 column by liquid chromatography coupled with tandem mass spectrometry. Many structure‐related compounds were included in these alkaloids fractions, which led to easy separation and good MS response in further work. Therefore, a search library of 52 benzylisoquinoline alkaloids was established, which included eight aporphine, 19 tetrahydroprotoberberine, two protopine, two benzyltetrahydroisoquinoline, and 21 protoberberine alkaloids. The information of the search library contained compound names, structures, retention times, accurate masses, fragmentation pathways of benzylisoquionline alkaloids, and their sources from three herbal medicines. Using such a library, the alkaloids, especially those trace and unknown components in some herbal medicine could be accurately and quickly identified. In addition, the distribution of benzylisoquinoline alkaloids in the herbal medicines could be also summarized by searching the source samples in the library.     

On an M (X)/G/1 Retrial System with Two Types of Search of Customers from the Orbit

Single server retrial queueing models in which customers arrive according to a batch Poisson process are considered here. An arriving batch, finding the server busy, enters an orbit. Otherwise, one customer from the arriving batch enters for service immediately while the rest join the orbit. The customers from the orbit (the orbital customers) try to reach the server subsequently with the inter-retrial times exponentially distributed. Additionally, at each service completion epoch, two different search mechanisms, that is, type I and type II search, to bring the orbital customers by the system to service, are switched on. Thus, when the server is idle, a competition takes place among primary customers, customers who come by retrial and by two types of searches. The type I search selects a single customer whereas the type II search considers a batch of customers from the orbit. Depending on the maximum size of the batch being considered for service by a type II search, two cases are addressed here. In the first case, no restriction on batch size is assumed, whereas in the second case, maximum size of the batch is restricted to a pre-assigned value. We call the resulting models as model 1 and model 2 respectively. In all service modes other than type II search, only a single customer is qualified for service. Service times of the four types of customers, namely, primary, repeated, and those who come by two types of searches are arbitrarily distributed (with different distributions which are independent of each other). Steady state analysis is performed and stability conditions are established. A control problem for model 2 is considered and numerical illustrations are provided.     

Hierarchical approach for survivable network design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.